\documentclass{ctexart}
\usepackage[top = 1.25in, bottom=1in, left=1in, right=1in]{geometry}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{listings}
\usepackage{algorithmic}
\usepackage{ifthen}
\usepackage{color}
\usepackage{latexsym}

\definecolor{grey}{rgb}{0.3,0.3,0.3}
\definecolor{darkgreen}{rgb}{0,0.3,0}
\definecolor{darkblue}{rgb}{0,0,0.3}
\definecolor{lightgrey}{rgb}{0.9,0.9,0.9}
\definecolor{darkgrey}{rgb}{0.1,0.1,0.1}

\lstset{
    basicstyle=\ttfamily,
    frame=single,
    extendedchars=false,
    escapechar=`,
    language=SQL
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Note For Database Management System            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{fancyhdr}
\fancyhead[C]{《数据库系统提纲》~~~~~~~~~学号：1080310226~~~~~~~~~姓名：刘一佳}
\fancyhead[L]{}\fancyhead[R]{}
\makeatletter
\def\headrule{{\if@fancyplain\let\headrulewidth\plainheadrulewidth\fi%
    \hrule\@height 1.0pt \@width\headwidth\vskip1pt%
    \hrule\@height 0.5pt\@width\headwidth%
    \vskip-2\headrulewidth\vskip-1pt}}
\makeatother
\pagestyle{fancy}

\begin{document}
    \title{数据库系统复习提纲}
    \maketitle
    \pagebreak
    \tableofcontents
    \section{数据库系统概述}
        \subsection{数据库、数据库管理系统和数据库}
            \subsubsection{数据库}
                \begin{itemize}
                    \item \textbf{定义} 数据库是相互关联的数据集合。
                    \item \textbf{特征}
                        \begin{enumerate}
                            \item 数据库是具有逻辑关系和确定意义的数据集合。逻辑上无关的数据集合不能称为数据库
                            \item 数据库是针对明确的应用目标而设计、建立和加载的。么个数据库都有一组用户，并为这些用户服务
                            \item 一个数据库表示了现实世界的某个方面，一个数据库所表示的现实世界的改变必须及时地反映到该数据库中
                        \end{enumerate}
                \end{itemize}
            \subsubsection{数据库管理系统}
                软件系统，由一组计算机程序组成，能够对于数据库进行有效的管理。
            \subsubsection{数据库系统}
                数据库和数据库管理系统加在一起构成\textbf{数据库系统}
        \subsection{数据库系统的特点与功能}
            \subsubsection{文件系统的缺点}
                \begin{itemize}
                    \item 数据共享性差，冗余度大
                    \item 数据不一致\{指的是数据的存储结构不同，有些有某项属性有些没有，就很混乱\}
                    \item 数据独立性差\{文件结构与程序关系紧密，文件系统依赖于程序，所以独立性较差\}
                    \item 数据的结构化程度低
                \end{itemize}
            \subsubsection{数据库系统的特点}
                \begin{itemize}
                    \item 信息完整、功能通用
                    \item 程序与数据独立
                    \item 数据抽象
                    \item 支持数据的不同视图
                    \item 控制数据冗余
                    \item 支持数据共享
                    \item 限制非授权的存取
                    \item 提供多种用户界面
                    \item 表示数据之间的复杂联系
                    \item 完整性约束
                    \item 数据恢复
                \end{itemize}
        \subsection{数据库系统的用户}
            \begin{itemize}
                \item 数据库管理员
                \item 数据库设计者
                \item 最终用户
                \item 系统分析员和应用程序员
                \item 与系统有关的其他人员
            \end{itemize}
        \subsection{数据抽象}
            \subsubsection{数据抽象与数据库的三种模式}
                \begin{itemize}
                    \item \textbf{视图级抽象} 把现实世界抽象为数据库外模式
                    \item \textbf{概念级抽象} 把数据库外的模式抽象为数据库的概念模型
                    \item \textbf{物理级抽象} 把数据库的概念模式抽象为数据库内的模式
                \end{itemize}
            \subsubsection{数据独立性}
                \begin{itemize}
                    \item 物理数据独立性
                    \item 逻辑数据独立性
                \end{itemize}
        \subsection{数据模型}
            \subsubsection{基于对象的数据模型}
                \begin{itemize}
                    \item 实体-联系模型
                    \item 面向对象的数据模型
                \end{itemize}
            \subsubsection{基于记录的数据模型}
                \begin{itemize}
                    \item 关系数据模型
                    \item 网络数据模型
                    \item 层次数据模型
                \end{itemize}
            \subsubsection{物理数据模型}
        \subsection{数据库语言}
            \begin{itemize}
                \item 数据库定义子语言
                \item 数据库操纵子语言
            \end{itemize}
        \subsection{数据库管理系统的结构}
        \subsection{数据库技术的发展}
        \subsection{习题}
            \subsubsection{什么是数据库，什么是数据库管理系统，什么是数据库系统}
                数据库是相互关联的数据集合\\
                数据库管理系统是由一组软件组成的管理数据库的软件系统\\
                数据库系统是数据库和数据库管理系统的总和
            \subsubsection{简述文件系统的缺点}
                \begin{itemize}
                    \item 共享性差，冗余
                    \item 结构不一致
                    \item 独立性差
                    \item 结构化程度低
                \end{itemize}
            \subsubsection{试说明数据字典的主要内容}
            \subsubsection{试述数据库系统的特点}
                \begin{itemize}
                    \item 信息完整、功能通用
                    \item 程序与数据独立，(对应文件系统中独立性差一特点)
                    \item 数据抽象，(数据的存储结构对于用户透明)
                    \item 支持数据的不同视图(不同的应用程序和用户，看到的数据库不同)
                    \item 控制数据冗余
                    \item 支持数据共享
                    \item 限制非授权的存取
                    \item 提供多种用户界面
                    \item 表示数据之间的复杂联系
                    \item 完整性约束
                    \item 数据恢复
                \end{itemize}
    \section{关系数据库系统}
        1970年E.F.Codd在ACM上发表了"Relational Model of Data for Shared Data Banks"的论文，开创了数据库系统的新纪元。从此，人们开始了关系型数据库的研究
        \subsection{关系数据模型}
            关系数据模型是关系数据库的基础。关系数据模型由\textbf{数据结构}、\textbf{完整性约束规则}和\textbf{关系运算}三部分构成。
            \subsubsection{数据结构}
                \begin{itemize}
                    \item \textbf{定义2.1.1} \textbf{域}是一个\textbf{集合}
                    \item \textbf{定义2.1.2} 设$D_1...D_n$是n个域，$D_1...D_n$上的\textbf{笛卡尔乘积}定义为集合$\{(d_1,...,d_n)|d_i \in D_i, 1\le i \le n\}$
                    \item \textbf{定义2.1.3} 笛卡尔乘积$D_1\times...\times D_n$的任意一个子集合称为定义在域$D_1,...,D_n$上的\textbf{关系}\\
                        对于关系定义的一些限定和扩充
                        \begin{enumerate}
                            \item 关系数据模型中的关系必须是有限集合
                            \item 消除关系元组的有序性
                        \end{enumerate}
                    \item \textbf{定义2.1.4} 关系的属性是为关系域附加的名字，是表示现实世界中实体性质的抽象信息。每个属性所表示的域称为该\textbf{属性的值域}
                    \item \textbf{定义2.1.5}
                    \item \textbf{定义2.1.6} \textbf{关系模型}是一个系统R(U,D,DOM,I,F)
                        \begin{itemize}
                            \item U是属性集合
                            \item D是属性的域集合(也就是集合的集合)
                            \item DOM是U到D的映射
                            \item I是完整性约束
                            \item F是属性间的函数依赖关系
                        \end{itemize}
                \end{itemize}
            \subsubsection{完整性约束规则}
                关系需要一个或一组属性作为键以表示关系元组的惟一性
                \begin{itemize}
                    \item \textbf{定义2.1.7} 关系模式R(U)的属性集合$kU$是\textbf{候选键}
                        \begin{enumerate}
                            \item R(U)的任何一个关系实例的任意两个元组在属性集合k上的值都不相同
                            \item k的任何真子集都不满足(1)
                        \end{enumerate}
                    \item 候选键必须是\textbf{唯一的}，而且是\textbf{最小的}。
                    \item 候选键可能具有多个，选择一个作为\textbf{主键}。
					\item 候选键中的属性称为\textbf{键属性}，其他属性称为\textbf{非键属性}。
					\item 主键中的属性称为\textbf{主属性}，其他属性称为\textbf{非主属性}。
                    \item 设X是关系模式R(U)的一个属性集合。如果X是另个一个关系模型$R'(U')$的主属性，则称X是R(U)关于$R'(U')$的\textbf{外部键}
                    \item \textbf{实体完整性约束} 如果A是关系模式R(U)的主属性，则A不能接受空值。
                    \item \textbf{关联完整性约束} 设X是关系模式R(U)关于$R'(U')$的外部键。如果K是R(U)的关系实例的一个元组的外部键的值，则$R'(U')$必然存在一个元组T，T在X值上为K
                \end{itemize}
        \subsection{关系运算}
            \subsubsection{关系代数}
                \begin{enumerate}
                    \item \textbf{并操作} 设R和S是n元关系，而且两者各对应属性的数据类型也相同。R和S的并操作定义为$R \cup S=\{t|t\in R \vee t \in S\}$
                    \item \textbf{差操作} 设R和S是n元关系，而且两者各对应属性的数据类型也相同。R和S的并操作定义为$R - S=\{t|t\in R \wedge t \in S\}$
                    \item \textbf{笛卡尔乘积} 设R是n元关系，S是m元关系，R和S的笛卡尔积的定义为\[R\times S = \{(r_1,...,r_n,s_1,...,s_n)|(r_1,...,r_n)\in R \wedge (s_1,...,s_n)\in S\}\]
                    \item \textbf{投影操作} 设R是一个n元关系，R的投影操作定义为\[\Pi_{i_1,i_2,...,i_m}(R)=\{(r_{i_1},...,r_{i_m})|(r_1,...,r_{i_1},...,r_{i_m},...,r_n)\in R,1\le i_1,...,i_m \le n\}\]
                    \item \textbf{选择操作}
                        设R是一个n元关系，F是一个形如$r_i\theta c$的公式，其中$\theta \in \{=,\neq,>,<,\le,\ge\}$,R的选择操作定义为\[\sigma_F(R)=\{r_1,...r_i,...r_n|(r_1,..,r_i,...,r_n) \in R \vee r_i \theta c\}\]
                    \item \textbf{交操作} 设R和S是n元关系，而且两者各对应属性的数据类型也相同。R和S的交操作定义为\[R\cap S=\{t|t\in R \vee t\in S\}=R-(R-S)\]
                    \item \textbf{连接} 设R是n元关系，S是m元关系，A是R的属性，B是S的属性，A和B的值域具有相同的数据类型，$\theta \in \{=,\neq,>,<,\le,\ge\}$。R和S的连接操作定义为\[R\Join_{A\theta B}S={rs|r\in R \vee s\in S \vee (r[A]\theta s[B])}=\sigma_{A\theta B}(R\times S)\]
                        \begin{itemize}
                            \item \textbf{自然连接} 连接属性同为B，连接条件为$R.B=S.B$
                            \item \textbf{复合连接}
                            \item \textbf{半连接}
                        \end{itemize}
                    \item \textbf{商操作}
                \end{enumerate}
            \subsubsection{元组关系演算}
            \subsubsection{域关系演算}
        \subsection{关系运算的安全性}

        \subsection{关系代数、元组演算、域演算的等价性}
        \subsection{关系数据库查询语言}
            \subsubsection{SQL语言}
                \begin{enumerate}
                    \item 数据定义
                        \begin{itemize}
                            \item 创建关系
                            \begin{lstlisting}
CREATE TABLE <`关系名`> (<`列名`> <`列类型`> [NOT NULL],...,
                            \end{lstlisting}
                            \item 修改关系
                            \begin{lstlisting}
ALTER TABLE <`关系名`> ADD <`列名`>
                            \end{lstlisting}
                        \end{itemize}
                    \item 数据查询
                        \begin{itemize}
                            \item 数据查询
                            \begin{lstlisting}
SELECT \text{[DISTINCT]} <`属性表`>
                            \end{lstlisting}
                        \end{itemize}
                    \item 数据维护
                        \begin{itemize}
                            \item 插入元组
                            \item 修改元组
                            \item 删除元组
                        \end{itemize}
                    \item 视图定义
                        \begin{itemize}
                            \item 定义视图
                            \begin{lstlisting}
CREATE VIEW
                            \end{lstlisting}
                        \end{itemize}
                \end{enumerate}
        \subsection{SQL语句速记}
            创建数据库
            \begin{lstlisting}
CREATE DATABASE <`数据库名`>;
            \end{lstlisting}

            创建关系
            \begin{lstlisting}
CREATE TABLE <`关系名`> (
    <`列名`>, <`列类型`>, [NOT NULL],
    ...
);
            \end{lstlisting}

            删除数据库
            \begin{lstlisting}
DROP DATABASE <`数据库名`>;
            \end{lstlisting}

            删除关系
            \begin{lstlisting}
DROP TABLE <`关系名`>;
            \end{lstlisting}

            SQL SELECT
            \begin{lstlisting}
SELECT <`列名`> FROM <`关系名`>
SELECT * FROM <`关系名`>
            \end{lstlisting}

            SQL DISTINCT 之列出某列不同的值
            \begin{lstlisting}
SELECT DISTINCT <`列名`> FROM <`关系名`>
            \end{lstlisting}

            SQL 关系运算
            \begin{lstlisting}
<`关系运算`>=<`列名`> <`关系运算符`> <`值`>
            \end{lstlisting}
            \begin{tabular}{|l|l|}
                \hline
                操作符  & 描述\\
                \hline
                $=$       & 等于\\
                $<>$      & 不等于\\
                $>$       & 大于\\
                $<$       & 小于\\
                $>=$      & 大于等于\\
                $<=$      & 小于等于\\
                $BETWEEN$ & 在某一范围内\\
                $LIKE$    & 搜索某种模式\\
                \hline
            \end{tabular}

            SQL WHERE 规定选择的标准
            \begin{lstlisting}
SELECT <`列名`> FROM <`关系名`> WHERE <`关系运算`>
            \end{lstlisting}

            SQL AND \&\& OR 用多于一个条件对记录进行过滤

            SQL ORDER BY 结果集进行排序
            \begin{lstlisting}
`单级排序` ORDER BY <`列名`> [`排序方式`]
`多级排序` ORDER BY <`列名1`> [`排序方式1`], <`列名2`> [`排序方式2`], ...
[`排序方式`]=[DESC|ASC]
[`排序方式`]`有降序DESC和升序ASC两种，默认为升序`
            \end{lstlisting}

            SQL INSERT INTO
            \begin{lstlisting}
INSERT INTO <`关系名`> VALUE(<`值1`>,<`值2`>,...);
INSERT INTO <`关系名`> VALUES(
    (<`元组1值1`>,<`元组1值2`>,...),
    (<`元组2值1`>,<`元组2值2`>,...),
    ...
);
INSERT INTO <`关系名`> (<`列1`>, <`列2`>, ...) VALUE(<`列1值1`>,<`列2值2`>,...);
INSERT INTO <`关系名`> (<`列1`>, <`列2`>, ...) VALUES(
    (<`元组1列1值1`>,<`元组1列2值2`>,...),
    (<`元组2列1值1`>,<`元组2列2值2`>,...),
    ...
);
            \end{lstlisting}

            SQL UPDATE
            \begin{lstlisting}
UPDATE <`关系名`> SET <`列名`>=<`新值`> WHERE <`关系运算`>
UPDATE <`关系名`> SET <`列名1`>=<`新值1`>,<`列名2`>=<`新值2`>,... WHERE <`关系运算`>
            \end{lstlisting}

            SQL LIKE
            \begin{lstlisting}
SELECT <`列名`> FROM <`关系名`> WHERE <`列名`> LIKE <`模式`>
            \end{lstlisting}

            SQL IN
            \begin{lstlisting}
SELECT * FROM Persons
WHERE LastName IN ('Adams','Carter')
            \end{lstlisting}

            SQL Group By
            \begin{lstlisting}
SELECT <`列名`>, <`聚集函数`> FROM <`关系名`>
    WHERE <`列名`> <`关系运算`> <`值`>
    GROUP BY <`列名`>
            \end{lstlisting}
            注意，对于所有的聚集函数，都是对于分组内进行运算
            
            SQL LEFT JOIN
            \begin{lstlisting}
SELECT <`列名`> FROM 
    <`关系名1`> LEFT JOIN <`关系名2`> ON <`关系名1`>.<`列名1`>=<`关系名2`>.<`列名2`>
            \end{lstlisting}
            
            SQL VIEW
            \begin{lstlisting}
CREATE VIEW <`视图名`> AS
    SELECT <`列名`> FROM <`关系名`> WHERE <`条件表达式`>

-- VIEW EXAMPLE --
-- CREATE VIEW --
CREATE VIEW [Category Sales For 1997] AS
    SELECT DISTINCT CategoryName, Sum(ProductSales) AS CategorySales
    FROM [Product Sales for 1997]
    GROUP BY CategoryName 
-- CALL VIEW --
SELECT * FROM [Category Sales For 1997]
            \end{lstlisting}
            
            SQL Trigger
            \begin{lstlisting}
-- INSERT TRIGGER --
CREATE TRIGGER <`触发器名`>
    ON jobs FOR { INSERT | UPDATE | DELETE }
    AS {
        <`SQL语句块`>
    }
            \end{lstlisting}

        \subsection{习题}
            \begin{enumerate}
                \item 试解释下列概念：
                    \begin{itemize}
                        \item \textbf{笛卡尔乘积} 设$D_1,...,D_n$是n个域。$D_1,...,D_n$上的笛卡尔乘积定义为集合
                            \[D_1\times ... \times D_n=\{(d_1,...,d_n)|d_i\in D_i\}\]
                        \item \textbf{关系} 笛卡尔乘积的一个子集
                        \item \textbf{属性} 关系的属性是为关系的域附加的名字
                        \item \textbf{属性值域} 每个属性所代表的域称为该属性的值域
                        \item \textbf{元组}
                        \item \textbf{关系模式}
                        \item \textbf{候选键} 唯一确定，各不相同
                        \item \textbf{主键}
                    \end{itemize}
                \item 试述关系数据模型的实体完整性约束和关联完整性约束
                \item 试回答下列问题
                    \begin{enumerate}
                        \item 可以表示任何关系代数的五种基本操作是什么？
                        \item 连接、等值连接、自然连接、半连接都是什么
                        \item 元组的关系演算表达式和域演算表达式的区别是什么
                        \item 元组的关系演算表达式的安全性定义是什么？
                        \item 域关系演算表达式的安全性定义是什么？
                    \end{enumerate}
            \end{enumerate}
    \section{数据库的安全性与完整性}
        \subsection{安全性}
            数据库的安全性只在保证数据库的任何部分都不受到恶意侵害或未经授权的存取和修改。主要考虑三方面问题
            \begin{itemize}
                \item 用户授权问题
                \item 防止非授权用户使用系统的问题
                \item 统计数据库的安全性
            \end{itemize}
            \begin{itemize}
                \item \textbf{数据库的安全性与数据库管理员} \\
                数据库管理员可以进行的操作有
                \begin{enumerate}
                    \item 建立账号
                    \item 撤销账号
                    \item 授予权利
                    \item 撤销权利
                \end{enumerate}
                \item \textbf{系统保护机制} \\
                \item \textbf{授权机制} \\
                    数据库管理系统一般都提供两种权限
                        \begin{enumerate}
                            \item 用户级权限 包括CREATE TABLE、CREATE VIEW、SELECT\
                            \item 关系级权限
                        \end{enumerate}
                    举例
                        \begin{itemize}
                            \item 授权A建立关系
                                \begin{lstlisting}
GRANT CREATETAB TO A
                                \end{lstlisting}
                            \item 用户A授权用很好B在EMPLOYEE和DEPARTMENT关系上插入好删除元组的权利，但不允许B把这些权利授予其他用户
                                \begin{lstlisting}
GRANT INSERT, DELETE ON EMPLOYEE, DEPARTMENT TO B
                                \end{lstlisting}
                        \end{itemize}
                \item \textbf{统计数据库的安全性}
            \end{itemize}
        \subsection{完整性}
            数据库完整性约束是保证数据库语义正确的关键。为了确保数据的完整性，数据库管理系统需要提供完整性约束定义和验证机制。
            \subsubsection{完整性约束的类型}
                \begin{enumerate}
                    \item 数据模型确定的完整性约束 \\
                        \textbf{关系模型} 关键字、实体完整性约束和关联完整性约束是关系模型隐含约束的实例。关系模型的约束很多，例如，具有第一范式的关系模型所有的属性值必须是原子数据。
                    \item 由应用确定的完整性约束 \\
                        \textbf{状态约束} \\ 在某一时刻数据库中的所有实例构成了一个状态，数据库的状态约束是所有数据库状态必须满足的约束。包括
                        \begin{enumerate}
                            \item 属性值域的约束，例如年龄有值域
                            \item 属性唯一性的约束，看名字比较容易理解
                            \item 属性结构约束，这种约束给定一个属性是单值属性还是多值属性，能否为空。
                            \item 联系结构约束，ER和EER模型中会用到
                            \item 超类/子类约束
                            \item 一般的语义完整性约束
                        \end{enumerate}
                        \textbf{变迁约束} \\
                        一个变迁约束的例子是“雇员的工资属性值只能增加”
                \end{enumerate}
            \subsubsection{显式约束的定义}
                \begin{enumerate}
                    \item 显式约束的过程化定义方法\\
                    显式约束的过程化定义方法是把显式约束作为一个过程，由程序员编码到更新数据库事务中。例如，要定义“员工工资不能高于项目经理”可以在有关数据库的更新事务中增加验证雇员工资不高于经理的过程。
                    \item 显式约束的断言定义方法\\
                    \item 触发器\\
                    在很多情况下，当一个完整性约束被违背时，数据库管理系统除了终止事务外，还需要执行一些其他操作，例如，通知某个用户完整性约束被违背。\\
                    一个触发器用来定义一个条件以及在该条件为真时需要执行的动作。
                \end{enumerate}
            \subsubsection{完整性约束的验证}
        \subsection{习题}
            \begin{enumerate}
                \item 什么是数据库的安全性\\
                数据库的安全性指数据库的任何部分都不允许受到恶意侵害和未经授权的存取和修改。
                \item 试述数据管理系统的保护机制\\
                如果一个用户需要使用数据库系统，该用户必须先向数据集管理员申请用户账号。如果该用户申请的数据的要求合理，数据库管理员将为这个用户创建一个新账号，并分配给一个口令字。
                \item 试述SQL语言的授权机制，即权限种类、授权命令和撤销权限命令\\
                \item 试回答下面问题
                    \begin{itemize}
                        \item 什么是隐含约束？\\
                        由数据库的数据结构据顶的约束
                        \item 什么是显示约束？\\
                        由用户实际需求产生的约束，比如，人的寿命应该大于等于1小于150
                        \item 什么是状态约束？\\
                        状态是数据库某一时刻的情况，
                        \item 什么是变迁约束？\\
                        数据库状态发生变化时需要遵照一定的约束，比如说“员工的工资只能增加”
                        \item 关系模型数据库具有哪些固有约束\\
                        比如说，第一范式要求属性都是原子的。
                    \end{itemize}
            \end{enumerate}
    \section{数据库设计概述与需求分析}
        \subsection{数据库设计概述}
            \subsubsection{数据库设计问题}
                \textbf{约束条件}
                \begin{itemize}
                    \item 计算机软硬件环境
                    \item 数据库管理系统的能力
                    \item 用户的操作要求与信息要素
                    \item 完整性和安全性约束
                \end{itemize}
            \subsubsection{数据库的生命周期}
            \subsubsection{数据库设计过程}
                \begin{enumerate}
                    \item 需求分析
                    \item 概念数据库设计
                    \item 逻辑数据库设计
                    \item 物理数据库设计
                \end{enumerate}
        \subsection{需求分析}
            需求分析的步骤如下
            \begin{enumerate}
                \item 应用领域的调查分析
                \item 定义数据库支持的信息与应用
                \item 定义数据库操作任务
                \item 定义数据字典
                \item 预测应用领域的未来改变
            \end{enumerate}
            \subsubsection{应用领域的调查分析}
                应用领域的调查分析包括两个阶段，\textbf{第一阶段}对于应用领域的组织结构，业务流程和数据流程进行调整，对现行系统的功能和所需信息进行明确认识；\textbf{第二阶段}在第一阶段的基础上进行应用领域的分析，抽象出应用领域的逻辑模型。

                第一阶段的使用方法如下：
                \begin{enumerate}
                    \item 调查给定应用领域的组织机构，列出各职能部门及相互关系
                    \item 对于每个职能部门，
                \end{enumerate}
                第二阶段的使用方法如下：
                \begin{enumerate}
                    \item
                \end{enumerate}
            \subsubsection{定义数据库系统支持的信息与应用}
            \subsubsection{定义数据操作任务}
            \subsubsection{定义数据项}
            \subsubsection{}
    \section{概念数据库设计}
        \subsection{概述}
            概念数据库设计包括两方面内容，\textbf{概念数据库模式设计}和\textbf{事务设计}
            \begin{itemize}
                \item 事务分析的任务是考察需求分析中提出的数据库操作任务，形成高级需求说明。
                \item 概念数据库模式设计的目标是
            \end{itemize}
            设计概念数据库的意义是：
            \begin{enumerate}
                \item 概念数据库模式设计的过程是彻底理解应用领域的信息结构、语义、信息的相互联系和各种约束的过程。
                \item 概念数据库模式是数据库内容的静态描述。
                \item
                \item 用图形化的方式表示概念数据库，直观易懂。
            \end{enumerate}
            概念设计阶段使用\textbf{语义数据模型}或\textbf{概念数据模型}，其特点是
        \subsection{实体联系模型}
            \subsubsection{实体和属性}
                \begin{itemize}
                    \item 实体联系模型简称\textbf{ER模型}。
                    \item \textbf{实体} 是ER模型的基本对象。实体是显示世界各种事物的抽象，可以是物理存在的事务，也可以是抽象概念
                    \item \textbf{属性} 每个实体的一组特征或性质
                    \item 某些属性具有多个独立的子属性，这样的属性被称为\textbf{复合属性}
                    \item 如果某个属性对于某一实体只有一个值，那么这个属性是\textbf{单值属性}
                    \item 如果某个属性对于某一实体有多个值，那么这个属性是\textbf{多值属性}，比如人的学位，因为一个人可能有多个学位。
                    \item 如果一个属性不是单独存储，而是由其他一些属性导出，那么这个属性被称为导出属性。
                \end{itemize}
            \subsubsection{实体型、键属性和属性的值域}
                \begin{itemize}
                    \item \textbf{实体型}是一个具相同属性的实体\textbf{集合}
                    \item 在ER模型中，每个实体型具有一个由一个或多个属性组成的\textbf{键}。
                    \item
                \end{itemize}
            \subsubsection{实体间的联系}
                一个数据库通常包含很多实体型，不同的实体型之间可能具有某种联系。我们称这种联系为实体间的联系。
                \begin{itemize}
                    \item 联系型和联系实例 设$E_1,E_2,..,E_n$是实体类型，$E_1,E_2,...,E_n$之间的联系型R定义为
                    \item 联系型的结构约束\\
                    例，如果在大学数据库中规定每个每个教研室必须有属于一个系，则教研室实体型上有一个与联系Belong\_To有关的关联约束：
                    \begin{center}
                        \textbf{每个教研室实体必须出现在一个Belong\_To实例中}
                    \end{center}
                    称这一类关联约束为\textbf{全局关联约束}。\\
                    由于并非每个老师都是系主任，所以老师实体型上有一个与联系T\_D\_2有关的实体关系约束，
                    \begin{center}
                        \textbf{教师实体型中仅有部分实体与系实体相关联}
                    \end{center}
                    这种实体关联约束称为\textbf{部分关联约束}
                    联系型上的\textbf{结构约束}可以统一定义为一耳光由实体型集合到整数对集合的映射F。
                    \item 联系型的属性
                \end{itemize}
            \subsubsection{弱实体}
            \subsubsection{实体联系图}
        \subsection{概念设计的方法与策略}
            \subsubsection{概念设计的方法}
            \subsubsection{概念设计的策略}
        \subsection{视图综合设计方法}
            \subsubsection{局部概念模式设计}
            \subsubsection{全局概念模式设计}
        \subsection{事务的设计}
    \section{逻辑数据库设计}
        \subsection{形成初始关系数据库模式}
            \begin{itemize}
                \item 普通实体型的变换
                \item 弱实体型的变换
                \item \textbf{多值属性的变换}\\
                    设实体型E具有多值属性，S是E对应的关系。我们为E的每个多值属性A建立一个关系T，用T表示A。
                    \begin{itemize}
                        \item 如果A是\textbf{简单属性}，那么T的属性是A和S的主键K
                        \item 如果A是\textbf{复合属性}，那么T包含A的所有子属性和S的主键K
                    \end{itemize}
                \item \textbf{实体间联系的变换}\\
                    \begin{enumerate}
                        \item \textbf{1:1联系的变换}
                            设有实体型$E_1$、$E_2$。关系S和T分别与之对应。
                            \begin{itemize}
                                \item 方法一\\
                                1. 将T的主键作为外键加入到S中\\
                                2. 将R的简单属性和复合属性的简单子属性作为简单属性填入S中。\\
                                3. 如果S和T中有一个具有关于R的全局关联约束，那么应该选择这个关系表示R\\
                                4. 如果S和T都具有关于R的全局关联约束，那么可以将S和T合并为一个关系型来表示R
                                \item 方法二\\
                                1. 建立一个单独的关系W表示R\\
                                2. 将T和S的主键作为键填入W\\
                                3. 将R的简单属性和符合属性的简单子属性作为简单属性填入W中。
                            \end{itemize}
                        \item \textbf{1:N联系的变换}
                            设R是从实体型$E_1$到实体型$E_2$的1:N联系,S和T是$E_1$和$E_2$对应的关系
                            \begin{itemize}
                                \item 方法一\\
                                1. S的主键作为外键填入T\\
                                2. R的简单属性和复合属性的简单子属性作为子属性填入T
                                \item 方法二\\
                                同\textbf{1:1的方法二}
                            \end{itemize}
                        \item \textbf{M:N联系的变换}
                            同\textbf{1:1的方法二}
                    \end{enumerate}
                \item 确定函数依赖集
            \end{itemize}
        \subsection{关系数据库设计理论}
            \subsubsection{问题提出}
                函数依赖是通过关系中属性值的相等与否体现出来数据间的相互关系。如，“学号”与“专业”这两个属性具有意义对应的关系。同样的情况还发生在
                \begin{itemize}
                    \item “学号”确定“姓名”($S\#\rightarrow SN$)
                    \item “学号”确定“系名”($S\#\rightarrow SD$)
                \end{itemize}
                假设经过抽象，得到了属性集U上的一个函数依赖集$F=\{S\#\rightarrow SD, SD\rightarrow MN,(S\#,CN)\rightarrow G\}$，然后又有关系$R(S\#,SD,MN,CN,G)$\\
                这个关系模式具有三个问题
                \begin{enumerate}
                    \item 插入异常
                    \item 删除异常
                    \item 数据冗余
                \end{enumerate}
            \subsubsection{函数依赖}
                \begin{description}
                    \item[一些约定] ~
                        \begin{itemize}
                            \item 设R是关系模式，U是R的属性集合，$X,Y\subset U$，$t\in R$(t是关系R上的一个元组)
                            \item $t[X]$表示元组t在属性集X上的值
                        \end{itemize}
                    \item[函数依赖] 对任意$t_1[X]=t_2[X]$有$t_1[Y]=t_2[Y]$
                    \item[非平凡函数依赖] 如果$X\rightarrow Y$而且Y不是X的子集
                    \item[决定属性集] 如果$X\rightarrow Y$，那么称X这个函数依赖的决定属性集
                    \item[X完全函数依赖Y] 如果$X\rightarrow Y$但是，任何X的子集Z都没有$Z\rightarrow Y$，那么称\textbf{Y完全函数依赖于X}。
                    \item[Z传递地函数依赖X] 设R是一个具有属性结合U的关系模式，$X\subseteq U,Y\subseteq U,Z\subseteq U,Y\rightarrow X$不成立，$Z-X,Z-Y,Y-X$不空。如果$X\rightarrow Y,Y\rightarrow Z$，则称Z传递地函数依赖于X。
                    \item[候选键] ~
                        \begin{enumerate}
                            \item $K\rightarrow U$
                            \item 不存在K的真子集Z使得$Z\rightarrow U$
                        \end{enumerate}
                    \item[主键] 候选键可能有多个，指定一个作为\textbf{主键}
                    \item[键属性] 包含在某一候选键中的属性是\textbf{键属性}
                    \item[非键属性] 不包含在任何候选键中的属性叫\textbf{非键属性}
                    \item[外部键] 如果X是关系模式R的属性子集合，而且X是另一关系模式的候选键，则称X是R的外部键。
                \end{description}
            \subsubsection{函数依赖的公理系统}
                \begin{itemize}
                    \item Armstrong公理系统包含如下三条公理
                        \begin{description}
                            \item[自反律] 若$Y\subseteq X\subseteq U$，则F蕴含$X\rightarrow Y$。
                            \item[增广律] 若F蕴含$X\rightarrow Y, Z\subseteq U$，则F蕴含$XZ\rightarrow YZ$。
                            \item[传递律] 若F蕴含$X\rightarrow Y$和$Y\rightarrow Z$则F蕴含$X\rightarrow Z$
                        \end{description}
                    \item Armstrong公理系统的三条推论
                        \begin{description}
                            \item[合并规则] 如果$X\rightarrow Y,X\rightarrow Z$则$X\rightarrow YZ$
                            \item[伪传递规则] 如果
                            \item[分解规则]
                        \end{description}
                    \item 函数依赖集闭包 F逻辑蕴含的所有函数依赖称为F的\textbf{闭包}，也就是利用现有函数依赖集能推导出的函数依赖集。
                    \item 属性集关于函数依赖集的闭包 某一属性集根据函数依赖能够推导出的\textbf{属性集}
                    \item 计算属性集的闭包的算法\\
                        \textbf{输入}:属性集X,函数依赖集F\\
                        \textbf{输出}:属性集关于函数依赖集的闭包$X^+$
                        \begin{lstlisting}[numbers=left]
`令X(1)为空,X(0)为X`
`枚举函数依赖集中所有的函数依赖`
    `如果决定属性集在X(0)中出现,那么把推出属性集加入B中`
`令X(1)为B与X(0)的并集`
`如果X(0)=X(1)`
    `那么算法终止`
`否则`
    `令X(0)=X(1)跳到第二步`
                        \end{lstlisting}
                    \item 函数依赖的等价性 \\
                        如果$G^+=F^+$，那么F与G等价
                    \item 极小函数依赖集
                        \begin{enumerate}
                            \item F中任意函数依赖的右部仅含有一个属性
                            \item F中不存在函数依赖$X\rightarrow A$，使得$F$与$F-{X\rightarrow A}$等价。
                            \item
                        \end{enumerate}
                    \item 每个函数依赖集都等价于一个极小函数依赖集。
                    \item 求极小函数依赖集的算法
                        \begin{lstlisting}
`枚举函数依赖集中的所有函数依赖X->Y,如果Y=A1...Ak,那么用X->A1,...,X->Ak代替X->Y`
`枚举所有函数依赖X->A,G=F-{X->A},如果A可以被X通过G推出，就去掉这一个函数依赖`
`枚举各函数依赖X->A,如果X=B1...Bm,则枚举Bi如果X-Bi可以推出A,那么用X-Bi->A代替X->A`
                        \end{lstlisting}
                \end{itemize}
            \subsubsection{关系模式的规范形式}
                \begin{description}
                    \item[第一范式(1NF)]
                        如果每个属性都是不可分的简单数据项的集合，那么这一关系模式为\textbf{第一范式关系模式}
                    \item[第二范式(2NF)]
                        如果关系模式R是1NF，而且每个\textbf{非主属性}都完全依赖于R的\textbf{键}，那么R为\textbf{第二范式关系模式}，记为2NF。
                    \item[第三范式(3NF)]
                        如果关系模式R是2NF，而且每个\textbf{非键属性}都不传递依赖于任何候选键，则称R为\textbf{第三范式关系模式}
                    \item[BCNF]
                        对于R的每个函数依赖$X\rightarrow Y$，X必为候选键
                            \begin{itemize}
                                \item 所有的\textbf{非键属性}都完全函数依赖于\textbf{每个}候选键
                                \item 所有的\textbf{键属性}都完全函数依赖于\textbf{每个}不含它的键属性
                                \item 没有任何属性完全函数依赖于非键属性
                            \end{itemize}
                \end{description}
            \subsubsection{多值依赖与第四范式}
                \begin{description}
                    \item[多值依赖] 设R是一个具有属性集合U的关系模式，X、Y和Z是U的子集，并且Z=U-X-Y，当r在(X,Z)上的每个值对应\textbf{一组}Y值，这组值只与X有关而与Z值无关。
                    \item[第四范式] 如果每个多值依赖$X\rightarrow\rightarrow Y$，X都含有R的候选键，则R是第四范式。
                \end{description}
            \subsubsection{连接依赖和第五范式}
        \subsection{关系模式规范化方法}
            \subsubsection{无损连接性和函数依赖保持性}
                \begin{description}
                    \item[关系模式的分解] ~\\
                        设R是具有属性集合U的关系模式。R的一个分解定义为
                        \[\rho = \{R_1,R_2,...,R_n\}\]
                        其中，$R_i$的属性集合是$U_i$，而且$U=\cup U_i$。
                    \item[函数依赖集在某一分解上的投影] ~\\
                        设R是一个具有属性集合U和函数依赖集合F的关系模式，$\rho = \{R_1,...,R_n\}$是R的一个分解。F在$R_i$的属性集合$U_i$上的投影是$F_i=\{X\rightarrow Y|X\rightarrow Y \in F^+, X,Y\in U_i\}$
                    \item[各关系模式上投影的连接] $m_{\rho}(r)$
                    \item[无损连接] $r=m_{\rho}(r)$
                    \item[无损连接的判定算法] ~\\
                        \textbf{输入：}
                            \begin{itemize}
                                \item 关系模式$R(A_1,A_2,...A_n)$
                                \item R的函数依赖F
                                \item R的分解$\rho=\{R_1,...,R_k\}$
                            \end{itemize}
                        \textbf{输出：}$\rho$是否为无损连接
                        \begin{lstlisting}
`建立k*n的矩阵S`
`将矩阵填入bij`
`枚举所有分解i`
    `枚举所有属性j`
        `如果Ri包含Aj，那么S[i,j]=aj`
`枚举所有函数依赖X->Y`
    `对于在X列上具有相同符号的行`
        `如果Y列上对应有a就填a`
        `没有就填一个b`
`如果找到一行都是a，那么就是无损连接`
                        \end{lstlisting}
                    \item[连接保持性定义] 对于一个分解$\rho$，$F_i$是F在Ui上的投影，如果$F^+=(\cup F_i)^+$，则有保持性。
                    \item[连接保持性的判定算法] 按照定义判断即可
                \end{description}
            \subsubsection{关系模式分解算法}
                \begin{itemize}
                    \item 3NF分解算法\\
                        \textbf{输入：} 关系模式R，R的属性集U，最小函数依赖G，R是1NF\\
                        \textbf{输出：} 无损分解
                    \begin{lstlisting}

                    \end{lstlisting}
                \end{itemize}
        \subsection{关系模式的优化}
    \section{物理数据库设计}
    \section{物理存储结构}
        \subsection{数据库存储设备}
            \subsubsection{磁盘存储器}
                \begin{description}
                    \item[单面磁盘] 磁盘只有单面用来存储数据
                    \item[双面磁盘] 磁盘双面都用来存储数据
                    \item[固定头磁盘存储器]
                    \item[活动头磁盘存储器]
                    \item[磁盘存储器的读写单位] 磁盘块(扇区)
                    \item[磁盘块地址的形式]
                        \begin{tabular}{|l|l|l|}
                            \hline
                            圆柱号 & 面号 & 扇区号 \\
                            \hline
                        \end{tabular}
                \end{description}
            \subsubsection{磁带存储器}
                \begin{description}
                    \item[磁带] 磁带是一种顺序辅助存储器。如果要读写磁带的第i块数据，必须读前i-1块数据。
                    \item[磁带的作用] ~\\
                        \begin{itemize}
                            \item 磁盘的后援，存储数据的副本
                            \item 大型数据库文件，不常用数据或历史数据
                        \end{itemize}
                \end{description}
            \subsubsection{磁盘缓冲处理技术}

            \subsubsection{磁盘调度策略}
                \begin{enumerate}
                    \item 先来先服务
                    \item 近者优先策略
                    \item 全程移动扫描策略
                    \item 移动扫描策略
                    \item 分组扫描策略
                    \item 间歇式全程扫描策略
                \end{enumerate}
        \subsection{文件和文件记录}
            \begin{description}
                \item[数据通常在磁盘上的存放方法] 数据通常以\textbf{记录}的形式存在磁盘上的
                \item[记录] 记录是一组相关的数据值或数据项排列而成
                \item 每个数据项对应记录的一个域
                \item[定长文件记录]
                \item[变长文件记录]
                \item[文件块] 磁盘文件的记录必须划分成多个大小与磁盘块容量相同的块
                \item[跨块记录] 一个记录存储在多个磁盘块内
                \item[非跨块记录] 一个记录只存储在一个磁盘块内
                \item[跨块存储记录方法]
                \item[非跨块存储记录方法]
                \item[在磁盘上存储文件的方法] ~
                    \begin{itemize}
                        \item 连续存储方法
                        \item 链接存储方法
                        \item 索引存储方法
                    \end{itemize}
            \end{description}
        \subsection{无序文件}
        \subsection{有序文件}
        \subsection{HASH文件}
            \subsubsection{简单HASH方法}
                \begin{description}
                    \item[HASH算法] ~\\
                    \textbf{输入:} HASH的域值，二进制串\\
                    \textbf{输出:} HASH桶的编号
                    \begin{lstlisting}
`把V分成等长的K组，若最后一位数不足则末尾补0`
``
                    \end{lstlisting}
                    \item[对于HASH溢出的处理方法] ~
                    \begin{itemize}
                        \item 多重HzmASH
                        \item 链接法 对于每个桶设置一个磁盘块链表。链表的第一块存正常存储记录，其他块存溢出记录。
                    \end{itemize}
                \end{description}
            \subsubsection{动态HASH方法}
                初始，HASH文件只有一m个HASH桶。当记录增加，这个HASH桶溢出时，它被划分为两个HASH桶。原HASH桶中的记录也被分成两部分。HASH值的第一位为1的记录分配到一个HASH桶；HASH值的1第一位为0的被分配到另一个HASH桶中。
            \subsubsection{可扩展的HASH方法}
        \subsection{索引文件}
                \begin{description}
                    \item[索引域] 文件的索引通常定义在一个或一组域上，这组域叫\textbf{索引域}
                    \item[索引文件] 索引也是一种文件，叫\textbf{索引文件}
                    \item[数据文件] 相应地被建立索引的文件叫做\textbf{数据文件}
                    \item[索引记录或索引项] 索引文件的记录叫做\textbf{索引项}或\textbf{索引记录}
                    \item[索引项的结构] 索引项一般包含两个域\textbf{索引域值}和\textbf{索引指针}
                    \item[索引文件] 如果索引文件很大，可以对索引文件进行再索引，建立多级索引，其中二叉树、多叉树、B树就是多级索引的例子
                    \item[按照索引文件的结构分类] ~
                        \begin{itemize}
                            \item 稀疏索引
                            \item 稠密索引
                        \end{itemize}
                    \item[按照索引域的特点分类] ~
                        \begin{itemize}
                            \item \textbf{主索引} 索引域是数据文件的键(一种文件的域，可以用来区分数据文件)
                            \item \textbf{聚集索引} 索引记录的第二个域存多个指针，聚集索引。
                            \item \textbf{辅助索引} 索引域值不是主键的索引
                        \end{itemize}
                \end{description}
            \subsubsection{主索引}
                \begin{description}
                    \item[定义] 主索引是一个具有两个域的有序文件
                    \item[主索引文件的结构] 主索引文件记录的以一个域的数据类型与数据文件的键相同，存储索引域值，第二个域存储指向这个磁盘块地址的指针。
                \end{description}
            \subsubsection{聚集索引}
                \begin{description}
                    \item[定义] 如果有序文件的排序域是一个\textbf{非键域}，文件的不同记录在这个域上可能有相同的值，将这种排序域叫做\textbf{聚集域}。
                    \item[聚集索引的结构] 如果(K(i),P(i))是聚集索引的一个记录，则P(i)是数据文件中包含聚集域值为K(i)的记录的第一个磁盘块的地址。
                \end{description}
            \subsubsection{辅助索引}
                \begin{description}
                    \item[定义] 辅助索引是建立在数据文件非排序域上的索引。辅助索引文件也是有序文件。(理解一下就是对于非主键的域X，也建立索引)
                    \item
                \end{description}
            \subsubsection{多级索引}
                \begin{description}
                    \item[定义] 为索引文件建立索引
                \end{description}
        \subsection{B树与B+树索引结构}
            \subsubsection{索引树结构}
                \begin{description}
                    \item[索引树] 秩为P的索引树结构式衣柜满足下列条件的树型结构
						\begin{itemize}
							\item 每个节点保存信息有$(P_1,K_1,...,P_n,K_q)$，其中，每个P是指向节点的指针或空。K是索引域的值。有$K_1<K_2<...<K_q$
							\item 有P指向的所有的值，当$1<i<q$时，有$K_{i-1}<X<K_i$，当$i=1$式，$X<K_i$，当$i=q$时，$X>K_{q-1}$
						\end{itemize}
                \end{description}
            \subsubsection{B树索引结构}
				\begin{description}
					\item[定义] 一个秩为D的B树索引结构是一个满足下列条件的树形树状结构：
						\begin{itemize}
							\item 每个内节点保存$(TP_1,<K_1,DP_1>,TP_2,<K_2,DP_2>,...,TP_q,<K_q,DP_q>)$，其中$q\le D$，$TP_i$是树指针
							\item
						\end{itemize}
				\end{description}
            \subsubsection{B+树索引结构}
    \section{数据库管理系统的数据字典}
    \section{关系代数操作的实现算法}
        \subsection{查询处理的过程}
        \subsection{选择操作的实现算法}
            \begin{enumerate}
                \item 线性搜索算法
                \item 二元或插值搜索算法
                \item 主索引或HASH搜索算法
                \item 使用主索引查找多个满足条件的元组
                \item 使用聚集索引查找抖个瞒着条件的元组
                \item B+树索引算法
                \item 合取选择算法
                \item 使用符合索引的合取选择算法
                \item 使用元组指针交集的合取选择算法
            \end{enumerate}
        \subsection{笛卡尔乘积的实现算法}
            注意，这里笛卡尔乘积的实现算法在内存中的实现都是双层枚举。但是，考虑到由于元组大小与磁盘块的关系，而产生了不同的情况
            \begin{enumerate}
                \item \textbf{简单算法} 这个算法要求$B_R+B_R\times B_S+B_{R\times S}$块磁盘存取操作
                \item \textbf{主存算法} 如果$M\ge B_S+B_R$，我们可以首先把R和S读入主存，然后在主存中产生$R\times S$，这个算法要$B_R+B_S+R_{R\times S}$块磁盘存取。
                \item \textbf{半主存算法} 如果$B_R\ge B_S, B_S <M$，可以把小的S读入主存，并保留至少一块主存作为R的缓冲区，这种算法的磁盘存取次数与主存算法相同。
                \item \textbf{大关系算法} 如果$M\le B_R, M\le B_S$，将其中小的划分成$B_S \div (M - 1)$各子集合，每个子集合有M-1块。
                    \begin{lstlisting}
FOR i=1 TO Bs/(M-1)DO
    `读S的第i个子集合到SB`
    FOR j=1 TO Br DO
        `读R的第j块到RB`
        FOR RB`中的每个R元组r` DO
            FOR SB`中的每个S元组s` DO
                `产生元组(rs)，存入结果关系`
            ENDFOR
        ENDFOR
    ENDFOR
ENDFOR
                    \end{lstlisting}
                    算法要求$B_R\times(B_S/(M - 1))+B_S+B_{R\times S}$块磁盘存取
            \end{enumerate}
        \subsection{连接操作的实现算法}
            连接算法可以通过修改大关系算法获得，与大关系算法相似，这个算法也需要$B_R\times B_S/(M-1)+B_S+B_{R\times S}$次存取
            \begin{lstlisting}
FOR i=1 TO Bs/(M-1)DO
    `读S的第i个子集合到SB`
    FOR j=1 TO Br DO
        `读R的第j块到RB`
        FOR RB`中的每个R元组r` DO
            FOR SB`中的每个S元组s` DO
                IF r.A \theta s.B THEN `(rs)存入结果关系`
            ENDFOR
        ENDFOR
    ENDFOR
ENDFOR
            \end{lstlisting}
            \subsubsection{连接操作结果的估计}
                
            \subsubsection{连接操作实现算法}
                \begin{enumerate}
                    \item 循环嵌套算法
                    \item SORT\_MERGE算法 算法复杂度$O(B_R\log_M{B_R}+B_S\log_M{B_S}+B_R+B_S+U)$
                        \begin{lstlisting}
`按属性R.Ai值排序R`
`按属性S.Bi值排序S`
`扫描R和S一遍，形成T={R(k)S(m)|R(k)[Ai]=S(m)[Bj]}`
                        \end{lstlisting}
                    \item HASH算法
                    \item 索引连接算法
                \end{enumerate}
        \subsection{投影操作的实现算法}
        \subsection{集合的交、并、差实现算法}
    \section{事务处理技术之一：并发控制技术}
        \subsection{并发控制的必要性}
            \subsubsection{单用户与用户数据库系统}
                \begin{description}
                    \item 在数据库系统中任何一个存取或改变数据库内容的程序的运行称为一个\textbf{数据库事务}
                \end{description}
            \subsubsection{并发控制的必要性}
                如果不进行并发控制可能会出项的问题
                \begin{enumerate}
                    \item 数据更新丢失 
                    \item 临时值问题 (数据库的值是临时值，拿出后又原封不动放回就会出现临时值问题)
                    \item 错误的聚集运算 ()
                \end{enumerate}
        \subsection{事务模型}
            \subsubsection{事务中的读写操作}
            \subsubsection{事务的原子性}
                每个事务都必须满足如下性质:该事务中所有操作要么全部被成功第完成而且这些操作的结果永久第被存储到数据库中，要么这个事务对数据库和其他事务没有任何影响，我们称这个性质为事务的原子性。
                
                事务的原子性可能遭到破坏的因素有如下两个：
                \begin{enumerate}
                    \item 多个事务并发运行，不同事务的操作交叉运行
                    \item 事务在运行中间被强行停止
                \end{enumerate}
            \subsubsection{事务的状态}
                事务的状态
                \begin{itemize}
                    \item 活动状态
                    \item 部分提交状态
                    \item 失败状态
                    \item 异常结束状态
                    \item 提交状态
                \end{itemize}
            \subsubsection{事务的性质}
                \begin{itemize}
                    \item 原子性
                    \item 数据库正确保持性
                    \item 操作结果永久保持性
                    \item 独立性
                    \item 可串行性
                \end{itemize}
        \subsection{事务调度与可串行性}
            \subsubsection{事务调度}
            \subsubsection{调度的可串行性}
                \begin{itemize}
                    \item 调度的冲突等价性
                    \item 调度的效果等价性
                    \item 调度的状态等价性
                \end{itemize}
            \subsubsection{调度的可串行性测试}
        \subsection{基于锁的并发控制协议}
            \subsubsection{锁的概念}
                \begin{itemize}
                    \item \textbf{共享锁(S锁，读锁)} 如果事务获得了共享锁，事务可以读，但不能写
                    \item \textbf{互斥锁()} 可读可写锁 
                \end{itemize}
            \subsubsection{两段锁协议}
                \begin{enumerate}
                    \item 阶段1 加锁阶段，事务可以申请获得任何数据项上的任何类型的锁，但不能释放任何锁
                    \item 阶段2 解锁阶段。在这个阶段，事务可以失望任何数据项上的任何类型的锁，但不能再申请任何锁。
                \end{enumerate}
            \subsubsection{数据库图协议}
        \subsection{时间印协议}
        \subsection{其他并发控制技术}
        \subsection{插入和删除操作}
    \section{事务处理技术之二：数据恢复技术}
        数据库的恢复机构用来进行实物终止后的善后处理和系统故障处理，确保系统发生故障以后，数据库能够恢复到正确状态。
        \subsection{数据库恢复的必要性}
            \begin{itemize}
                \item 数据库系统的数据库恢复机构的目的有两个
                    \begin{itemize}
                        \item 保证事务的原子性
                        \item 当系统发生故障以后，数据库能够恢复到正确的状态。
                    \end{itemize}
                \item 破坏事务原子性和引起系统故障的原因有以下几种
                    \begin{enumerate}
                        \item 计算机系统故障
                        \item 事务或系统错误
                        \item 事务的强行终止
                        \item 磁盘故障
                        \item 其他原因
                    \end{enumerate}
                \item 数据的存储设备按其存取速度、容量和故障可恢复性分为三种
                    \begin{enumerate}
                        \item 非永久存储器
                        \item 永久存储器
                        \item 永恒存储器
                    \end{enumerate}
            \end{itemize}
        \subsection{使用日志的数据库恢复技术}
            \subsubsection{数据库系统日志}
                记录有关事务的数据库操作信息的存储结构式数据库系统日志，简称日志。每个日志记录描述一个数据库写操作，与WRITE(Q)对应的日志记录具有如下数据域
                \begin{enumerate}
                    \item 事务名：执行WRITE(Q)操作的事务名
                    \item 数据项名：Q的唯一名字
                    \item 原始值：Q在执行WRITE(Q)之前的值
                    \item 新值：Q在执行WRITE(Q)之后的值
                \end{enumerate}
            \subsubsection{推迟更新技术}
            \subsubsection{即时更新技术}
        \subsection{缓冲技术}
            \subsubsection{缓冲日志}
            \subsubsection{数据库缓冲技术}
        \subsection{检测点}
        \subsection{影子页面技术}
        \subsection{永久存储器中信息丢失后的数据库恢复}
        \subsection{数据库恢复与并发控制技术的结合}
\end{document}
